package day23;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。
 *
 * 岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。
 *
 * 你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成 一座岛 。
 *
 * 返回必须翻转的 0 的最小数目。
 *
 *
 *
 * 示例 1：
 *
 * 输入：grid = [[0,1],[1,0]]
 * 输出：1
 * 示例 2：
 *
 * 输入：grid = [[0,1,0],[0,0,0],[0,0,1]]
 * 输出：2
 * 示例 3：
 *
 * 输入：grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
 * 输出：1
 *
 *
 */
public class Solution1 {
    public int shortestBridge(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int [][]bfs={{0,-1},{0,1},{-1,0},{1,0}};
        Queue<int[]> queue = new LinkedList<>();
        List<int []> isLand = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(grid[i][j]==1){
                    grid[i][j]=-1;
                    queue.offer(new int[]{i,j});
                    while (!queue.isEmpty()){
                        int[] poll = queue.poll();
                        isLand.add(poll);
                        int x = poll[1];
                        int y = poll[0];
                        for (int k = 0; k < 4; k++) {
                            int xm = x+bfs[k][1];
                            int yn = y+bfs[k][0];
                            if(xm>=0&&yn>=0&&xm<m&&yn<n&&grid[yn][xm]==1){
                                grid[yn][xm]=-1;
                                queue.offer(new int[]{yn,xm});
                            }
                        }
                    }
                    for (int[] ints : isLand) {
                        queue.offer(ints);
                    }
                    int distance = 0;
                    while (!queue.isEmpty()){
                        int size = queue.size();
                        for (int k = 0; k < size; k++) {
                            int[] poll = queue.poll();
                            int x = poll[1];
                            int y = poll[0];
                            for (int l = 0; l < 4; l++) {
                                int xm = x+bfs[l][1];
                                int yn = y+bfs[l][0];
                                if(xm>=0&&yn>=0&&xm<m&&yn<n){
                                    if(grid[yn][xm]==0){
                                        grid[yn][xm]=-1;
                                        queue.offer(new int[]{yn,xm});
                                    }else if(grid[yn][xm]==1){
                                        return distance;
                                    }
                                }
                            }
                        }
                        distance++;
                    }
                }
            }
        }
        return 0;
    }
}
